/*
 * @lc app=leetcode.cn id=912 lang=javascript
 *
 * [912] 排序数组
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function(nums) {
  quick_sort(nums, 0, nums.length-1);

  function quick_sort(arr, l, r){
    if(l >= r) return;
    let x = l, y = r, base = arr[l];
    while(x<y){
      while(x<y && arr[y] >= base) y--;
      if(x<y)arr[x++] = arr[y];
      while(x<y && arr[x] <= base) x++;
      if(x<y)arr[y--] = arr[x];
    }
    arr[x] = base;

    quick_sort(arr, l, x-1)
    quick_sort(arr, x+1, r)
  }
  return nums;
};
// @lc code=end

